package com.learn.algorithm.exercises.nowcoder;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author wangxing
 * @version 2020/5/27 10:49 Administrator
 */
public class PinDuoduo {
    /*

     */

    /**
     * 多多鸡有N个魔术盒子（编号1～N），其中编号为i的盒子里有i个球。
     * <p>
     * 多多鸡让皮皮虾每次选择一个数字X（1 <= X <= N），多多鸡就会把球数量大于等于X个的盒子里的球减少X个。
     * <p>
     * 通过观察，皮皮虾已经掌握了其中的奥秘，并且发现只要通过一定的操作顺序，可以用最少的次数将所有盒子里的球变没。
     * <p>
     * 那么请问聪明的你，是否已经知道了应该如何操作呢？
     * 折半查找,每次从中间取值,然后会把整个数组每次分为两个一样的数组,然后再折半
     * 比如1,2,3,4,5,6,7,8,9,10
     * 第一次取10/2=5
     * 用5作为第一个数字
     * 得到
     * 1,2,3,4,0,1,2,3,4,5
     * 第二次再折半用5/2,四舍五入=3
     * 1,2,0,1,0,,0,0,0,1,2
     * 这么算下最小的总次数就是总数的lg(n)为多少
     *
     * @param n 盒子中球的总数量
     * @return
     */
    public static int getChangeBoxBallNumMinCount(int n) {
        int i = 0;
        while (n > 0) {
            i++;
            n = n >> 1;
        }
        return i;
    }

    /**
     * 数列 {An} 为N的一种排列。
     * 例如N=3，可能的排列共6种：
     * {
     * 1, 2, 3
     * 1, 3, 2
     * 2, 1, 3
     * 2, 3, 1
     * 3, 1, 2
     * 3, 2, 1
     * }
     * A 3 3
     * 定义函数F
     * F(X)=A1 (x=1)
     * F(x)=|F(x-1)-Ax|(x>1)
     * <p>
     * 其中|X|表示X的绝对值。
     * 现在多多鸡想知道，在所有可能的数列 {An} 中，F(N)的最小值和最大值分别是多少。
     */
    static class printNumArraysMaxMin {
        public int getMin(int num) {
            if (num % 4 == 0 || (num + 1) % 4 == 0) {
                return 0;
            } else {
                return 1;
            }
        }

        public int getMax(int num) {
            if (num == 1 || num == 2) {
                return 1;
            } else {
                return Math.abs(getMin(num - 1) - num);
            }
        }

        public int F(int[] arr) {
            int result = arr[0];
            int l = arr.length;
            for (int i = 1; i < l; i++) {
                result = Math.abs(result - arr[i]);
            }
            return result;
        }

        /**
         * 获取一个正序数组的全排列的下一个数组排列,知道当前这个正序数组完全逆序
         *
         * @param arr
         * @return
         */
        public int nextIndexArray(int... arr) {
            int l = arr.length;
            int i = 0;
            for (i = l - 1; i > 0; i--) {
                //arr[i-1]<arr[i]表示当前这个范围内是有序的
                if (arr[i - 1] < arr[i]) {
                    break;
                }
            }
            //如果一个有序的也没有,那么证明当前是最后一个
            if (i == 0) {
                return 0;
            }
            int j = 0;
            //第二步，arr[i-1]大的第一个数字。
            for (j = l - 1; j > i; j--) {
                if (arr[j] > arr[i - 1]) {
                    break;
                }
            }
            // 第三部，arr[i-1],arr[j]
            int temp = arr[i - 1];
            arr[i - 1] = arr[j];
            arr[j] = temp;
            while (i < l - 1) {
                temp = arr[i];
                arr[i] = arr[l - 1];
                arr[l - 1] = temp;
                i++;
                l--;
            }
            return 1;
        }

        public void printNumArraysMaxMin(int num) {
            int max = 0;
            int min = Integer.MAX_VALUE;
            int[] arr = new int[num];

            for (int i = 1; i <= num; i++) {
                arr[i - 1] = i;
            }
            int temp = 1;
            while (temp != 0) {
                max = Math.max(max, F(arr));
                min = Math.min(max, F(arr));
                temp = nextIndexArray(arr);
            }
            System.out.println(min + " " + max);
        }
    }

    /**
     * 在一块长为n，宽为m的场地上，有n✖️m个1✖️1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积
     * n = 3, m = 3
     * 1   2   3
     * 2   4   6
     * 3   6   9
     * 给出一个查询的值k，求出按照这个方式列举的的数中第k大的值v
     * k = 1, v = 9
     * k = 2, v = 6
     * k = 3, v = 6
     * ...
     * k = 8, v = 2
     * k = 9, v = 1
     */
    class NumberData {
        public int getIndexNumber(int n, int m, int k) {
            if (k > m * n) {
                throw new RuntimeException(" k is error data");
            }
            if (k == 1) {
                return m * n;
            } else if (k == m * n) {
                return 1;
            } else {
                ArrayList<Integer> arr = new ArrayList<>(m * n);
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= m; j++) {
                        arr.add(i * j);
                    }
                }
                Collections.sort(arr, new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 > o2 ? -1 : o1 == o2 ? 0 : 1;
                    }
                });
                return arr.get(k);
            }
        }
    }

    public static int getIndexNumber(int n, int m, int k) {
        if (k > m * n) {
            throw new RuntimeException(" k is error data");
        }
        if (k == 1) {
            return m * n;
        } else if (k == m * n) {
            return 1;
        } else {
            ArrayList<Integer> arr = new ArrayList<>(m * n);
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    arr.add(i * j);
                }
            }
            Collections.sort(arr, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 > o2 ? -1 : o1 == o2 ? 0 : 1;
                }
            });
            return arr.get(k);
        }
    }

    /**
     * 多多鸡打算造一本自己的电子字典，里面的所有单词都只由a和b组成。
     * 每个单词的组成里a的数量不能超过N个且b的数量不能超过M个。
     * 多多鸡的幸运数字是K，它打算把所有满足条件的单词里的字典序第K小的单词找出来，作为字典的封面。
     *
     * @param n 字典内a的上限数量
     * @param m 字典内b的上限数量
     * @param k 要查找字典内的索引位置
     * @return
     */
    public static String getDictionaryIndexStr(int n, int m, int k) {
        StringBuilder str = new StringBuilder(m + n);
        if (k <= n) {
            for (int i = 0; i < k; i++) {
                str.append("a");
            }
        } else if (k <= n + m) {
            for (int i = 0; i < n; i++) {
                str.append("a");
            }
            int t = m + n - k;
            for (int i = n - 1; i < t; i++) {
                str.append("b");
            }
        } else if (k > m + n) {
        }

        return str.toString();
    }
    //    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        int t = sc.nextInt();
//        for(int i=0;i<t;i++){
//            System.out.println(getChangeBoxBallNumMinCount(sc.nextInt()));
//        }
//    }
}
